class Solution {
public:
    int inf = 1000000007;
    pair<int, bool> dp[11][55][55];
    int ways(vector<string>& pizza, int k) {
        int n = pizza.size(), m = pizza[0].size();
        vector<vector<int>> arr(1, vector<int>(m + 1, 0));
        for (int i = 0; i < pizza.size(); i++)
        {
            arr.push_back(vector<int>(1, 0));
            for (int j = 0; j < pizza[i].size(); j++)
            {
                int temp = pizza[i][j] == 'A' ? 1 : 0;
                arr[i + 1].push_back(temp);
                arr[i + 1][j + 1] = arr[i + 1][j + 1] + arr[i][j + 1] + arr[i + 1][j] - arr[i][j];
            }
        }
        return dfs(k - 1, 1, 1, arr);
    }
    int find(int x, int y, vector<vector<int>>& arr)
    {
        return arr[arr.size() - 1][arr[0].size() - 1] - arr[x - 1][arr[0].size() - 1] - arr[arr.size() - 1][y - 1] + arr[x - 1][y - 1];
    }
    int dfs(int k, int x1, int y1, vector<vector<int>>& arr)
    {
        if (!k) return find(x1, y1, arr) >= 1 ? 1 : 0;
        if (!find(x1, y1, arr)) return 0;
        if (dp[k][x1][y1].second) return dp[k][x1][y1].first;
        int ans = 0;
        for (int i = x1 + 1; i < arr.size(); i++)
        {
            if (arr[i - 1][arr[0].size() - 1] - arr[i - 1][y1 - 1] - arr[x1 - 1][arr[0].size() - 1] + arr[x1 - 1][y1 - 1] == 0) continue;
            ans += dfs(k - 1, i, y1, arr);
            ans %= inf;
        }
        for (int i = y1 + 1; i < arr[0].size(); i++)
        {
            if (arr[arr.size() - 1][i - 1] - arr[arr.size() - 1][y1 - 1] - arr[x1 - 1][i - 1] + arr[x1 - 1][y1 - 1] == 0) continue;
            ans += dfs(k - 1, x1, i, arr);
            ans %= inf;
        }
        dp[k][x1][y1].second = 1;
        return dp[k][x1][y1].first = ans;
    }
};